#include <compat/queue.h>


/*



typedef struct
{
int x;
} my_point_t;


typedef struct
{
my_point_t point;
_queue_t queue;

} my_point_queue_t;

void dump_queue_from_tail(_queue_t *que)
{

_queue_t *q = _queue_last(que);

printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);

for (; q != _queue_sentinel(que); q = _queue_prev(q))
{
my_point_queue_t *point = _queue_data(q, my_point_queue_t, queue);
}

}

int my_point_cmp(const _queue_t* lhs, const _queue_t* rhs)

{

my_point_queue_t *pt1 = _queue_data(lhs, my_point_queue_t, queue);
my_point_queue_t *pt2 = _queue_data(rhs, my_point_queue_t, queue);
if (pt1->point.x % 2 == 0)
return 1;
return 0;
}


void dump_queue_from_head(_queue_t *que)
{

_queue_t *q = _queue_head(que);
printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);
for (; q != _queue_sentinel(que); q = _queue_next(q))
{

my_point_queue_t *point = _queue_data(q, my_point_queue_t, queue);

}

}



my_point_queue_t *point;
_queue_t* myque = malloc(sizeof(_queue_t));  //alloc a queue head
_queue_init(myque);

for (int i = 0; i < 100; i++) {

	point = malloc(sizeof(my_point_queue_t));
	point->point.x = i;
	_queue_init(&point->queue);
	_queue_insert_head(myque, &point->queue);
}



dump_queue_from_tail(myque);
_queue_sort(myque, my_point_cmp);
dump_queue_from_tail(myque);
*/


STD_METHOD(_queue_t*) queue_middle(_queue_t *queue)
{
	_queue_t  *middle	= NULL;
	_queue_t  *next		= NULL;

	middle = _queue_head(queue);

	if (middle == _queue_last(queue)) {
		return middle;
	}

	next = _queue_head(queue);

	for (;; ) {
		middle = _queue_next(middle);

		next = _queue_next(next);

		if (next == _queue_last(queue)) {
			return middle;
		}

		next = _queue_next(next);

		if (next == _queue_last(queue)) {
			return middle;
		}
	}
}


STD_METHOD(void) queue_sort(_queue_t *queue,int(*cmp)(const _queue_t *, const _queue_t *))
{
	_queue_t  *q, *prev, *next = NULL;


	q = _queue_head(queue);

	if (q == _queue_last(queue)) {
		return;
	}

	for (q = _queue_next(q); q != _queue_sentinel(queue); q = next) {

		prev = _queue_prev(q);
		next = _queue_next(q);

		_queue_remove(q);

		do {
			if (cmp(prev, q) <= 0) {
				break;
			}

			prev = _queue_prev(prev);

		} while (prev != _queue_sentinel(queue));

		_queue_insert_after(prev, q);
	}
}